#include <cstdio>
#include <cstring>
using namespace std;

const int maxn = 1010;
const int INF = 2000000;

int n, m, ans, ga[maxn][maxn], vi[maxn], v[maxn], from[maxn], more, q[maxn];

void init() {
	scanf("%d%d", &n, &m);
	for (int i=0;i<n;i++)
		for (int j=0;j<n;j++)
			ga[i][j] = INF;
	for (int i=1;i<=m;i++) {
		int x, y, c;
		scanf("%d%d%d", &x, &y, &c);
		//x++; y ++;
		ga[x][y] = c;
	}
}


bool find(int nu,int col)
{
	int i=nu;
	int tt=0;
	while (i!=0 && v[i]==false)
	{
		q[tt++]=i;
		v[i]=col;
		i=from[i];
	}
	int last=i;
	int j,k;
	if (i==0) return false;
	if (v[i]!=col) return false;
	for (i=0;i<tt;++i)
		if (q[i]==last) break;
	if (i==tt) return false;
	int tmp=0;
	for (j=i;j<tt;++j)
	{
		tmp+=ga[from[q[j]]][q[j]];
		if (j!=i) vi[q[j]]=1;
	}
	for (j=i+1;j<tt;++j)
		for (k=0;k<n;++k)
		if (!vi[k] && k!=last)
		{
			if (ga[q[j]][k]<ga[last][k]) ga[last][k]=ga[q[j]][k];
			if (ga[k][last]>ga[k][q[j]]-ga[from[q[j]]][q[j]]) ga[k][last]=ga[k][q[j]]-ga[from[q[j]]][q[j]];
		}
}
int msdt(int root)
{
	memset(vi,0,sizeof vi);
	bool f=1;
	int i,j,tmp=0;
	while (f)
	{
		f=0;
		for (i=0;i<n;++i)
		{
			if (i!=root && !vi[i])
			{
				int tmp=-1;
				for (j=0;j<n;++j)
					if (tmp==-1 || ga[j][i]<ga[tmp][i])
						tmp=j;
				if (tmp!=-1) from[i]=tmp;
			}
		}
		memset(v,0,sizeof v);
		for (i=0;i<n;++i)
			if (!vi[i] && !v[i] && i!=root) f|=find(i,++tmp);
	}
	int ans=0;
	for (i=0;i<n;++i)
		if (i!=root) ans+=ga[from[i]][i];
	return ans;
}
void work() {
	ans = msdt(0);
	if (ans >= INF) printf("Possums!\n"); else
	printf("%d\n", ans);
}

int main() {
//	freopen("I.in","r",stdin);
//	freopen("I.out","w",stdout);
	int T;
	scanf("%d", &T);
	for (int ti=1;ti<=T;ti++) {
		printf("Case #%d: ", ti);
		init();
		work();
	}
	return 0;
}

